class FHQTreap {
public:
    FHQTreap() {}
    FHQTreap(int n) {
        init(n);
    }

    void add(int num) {
        split(0, 0, head, num);
        Tree[++cnt].key = num;
        Tree[cnt].size = 1;
        Tree[cnt].priority = (double)rand() / RAND_MAX;
        head = merge(merge(Tree[0].rs, cnt), Tree[0].ls);
    }

    void remove(int num) {
        split(0, 0, head, num);
        int lm = Tree[0].rs;
        int r = Tree[0].ls;
        split(0, 0, lm, num - 1);
        int l = Tree[0].rs;
        int m = Tree[0].ls;
        head = merge(merge(l, merge(Tree[m].ls, Tree[m].rs)), r);
    }

    int rank(int num) {
        split(0, 0, head, num - 1);
        int ans = Tree[Tree[0].rs].size + 1;
        head = merge(Tree[0].rs, Tree[0].ls);
        return ans;
    }

    int index(int x) {
        return index(head, x);
    }

    int pre(int num) {
        return pre(head, num);
    }

    int post(int num) {
        return post(head, num);
    }
private:
    void init(int n) {
        head = cnt = 0;
        Tree.assign(n + 1, {});

    }

    void up(int i) {
        Tree[i].size = Tree[Tree[i].ls].size + Tree[Tree[i].rs].size + 1;
    }

    void split(int l, int r, int i, int num) {
        if(i == 0) {
            Tree[l].rs = Tree[r].ls = 0;
        } else {
            if(Tree[i].key <= num) {
                Tree[r].ls = i;
                split(i, r, Tree[i].rs, num);
            } else {
                Tree[r].ls = i;
                split(l, i, Tree[i].ls, num);
            }
            up(i);
        }
    }

    int merge(int l, int r) {
        if(l == 0 || r == 0) {
            return l + r;
        } else {
            if(Tree[l].priority >= Tree[r].priority) {
                Tree[l].rs = merge(Tree[l].rs, r);
                up(l);
                return l;
            } else {
                Tree[r].ls = merge(l, Tree[r].ls);
                up(r);
                return r;
            }
        }
    }

    int index(int i, int x) {
        if(Tree[Tree[i].ls].size >= x) {
            return index(Tree[i].ls, x);
        } else if(Tree[Tree[i].ls].size + 1 < x) {
            return index(Tree[i].rs, x - Tree[Tree[i].ls].size - 1);
        } else {
            return Tree[i].key;
        }
    }

    int pre(int i, int num) {
        if(i == 0) {
            return std::numeric_limits<int>::min();
        }
        if(Tree[i].key >= num) {
            return pre(Tree[i].ls, num);
        } else {
            return std::max(Tree[i].key, pre(Tree[i].rs, num));
        }
    }

    int post(int i, int num) {
        if(i == 0) {
            return std::numeric_limits<int>::max();
        }

        if(Tree[i].key <= num) {
            return post(Tree[i].rs, num);
        } else {
            return std::min(Tree[i].key, post(Tree[i].ls, num));
        }
    }

    struct Node {
        int ls, rs, size, key;
        double priority;
    };

    int head, cnt;
    std::vector<Node> Tree;
};